package leetcode.stack;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @Description: https://leetcode.cn/problems/daily-temperatures/
 * @Author Ammar
 * @Create 2023/7/12 12:01
 */
public class _739_每日温度 {

    // 单调递减
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures.length == 1) return new int[]{0};
        int[] answer = new int[temperatures.length];
        Stack<Integer> deque = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!deque.empty() && temperatures[deque.peek()] < temperatures[i]) {
                Integer pop = deque.pop();
                answer[pop] = i - pop;
            }
            deque.push(i);
        }
        return answer;
    }

    // 动态规划
    public int[] dailyTemperatures1(int[] temperatures) {
        if (temperatures.length == 1) return new int[]{0};
        int[] answer = new int[temperatures.length];
        for (int i = temperatures.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                } else if (answer[j] == 0) {
                    answer[i] = 0;
                    break;
                } else if (temperatures[j] == temperatures[i]) {
                    answer[i] = answer[j] + j - i;
                    break;
                } else { // t[i] > t[j]
                    j = j + answer[j];
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        new _739_每日温度().dailyTemperatures1(new int[]{73,74,75,71,69,72,76,73});
    }
}
